package graph;

//使用邻接表来表示图
public class GraphII {

	class GraphNode{
		int v;	//当前顶点的编号
		GraphNode next;
		public GraphNode() {
		}
		public GraphNode(int v) {
			this.v = v;
		}
	}
	
	int count = 0;	//顶点的个数
	int type;	//图的类型
	GraphNode[] lists;	//用以存储所有的链表结构
	
	//初始化图
	public GraphII(int n, int type) {
		count = n;
		lists = new GraphNode[n];
		this.type = type;
	}
	
	// 判断图的类型
	public int getType() {
		return type;
	}

	// 获取图的顶点数
	public int getVertexCount() {
		return count;
	}
	
	//插入边
	public void insertEdge(int u, int v){
		for(int i = 0; i < count; i++){
			if(lists[i].v == u){
				GraphNode node = new GraphNode(v);
				node.next = lists[i].next;
				lists[i].next = node;
				break;
			}
		}
		//如果是无向图，那么我们还需要将v指向u
		if(type == 0){
			for(int i = 0; i < count; i++){
				if(lists[i].v == v){
					GraphNode node = new GraphNode(u);
					node.next = lists[i].next;
					lists[i].next = node;
					break;
				}
			}
		}
	}
	
	//删除边
	public void deleteEdge(int u, int v){
		for(int i = 0; i < count; i++){
			if(lists[i].v == u){
				GraphNode pre = lists[i];
				GraphNode cur = lists[i].next;
				while(cur != null && cur.v != v){
					pre = cur;
					cur = cur.next;
				}
				pre.next = cur.next;
				cur.next = null;
			}
		}
		//如果是无向图，那么我们还需要删除v指向u的边
		if(type == 0){
			for(int i = 0; i < count; i++){
				if(lists[i].v == v){
					GraphNode pre = lists[i];
					GraphNode cur = lists[i].next;
					while(cur != null && cur.v != u){
						pre = cur;
						cur = cur.next;
					}
					pre.next = cur.next;
					cur.next = null;
				}
			}
		}
	}
	
	//判断两个顶点是否相邻接
	public boolean isAdjacent(int u, int v){
		for(int i = 0; i < count; i++){
			if(lists[i].v == u){
				GraphNode cur = lists[i];
				while(cur != null){
					if(cur.v != v){
						cur = cur.next;
					}else{
						return true;
					}
				}
				break;
			}
		}
		return false;
	}
	
	//计算顶点的度
	public int getDegree(int u){
		int degree = 0;
		//先计算单链表的长度
		//对于无向图，度即为单链表的长度
		for(int i = 0; i < count; i++){
			if(lists[i].v == u){
				GraphNode cur = lists[i];
				while(cur != null){
					degree++;
					cur = cur.next;
				}
			}
		}
		//对于有向图，还需要遍历整个链表数组计算入度
		for(int i = 0; i < count; i++){
			//不要从第一个开始，否则我们会将lists[u]的头结点计算在内
			GraphNode cur = lists[i].next;
			while (cur != null) {
				if(cur.v == u){
					degree++;
					break;
				}else{
					cur = cur.next;
				}
			}
		}
		return degree;
	}
	
	//计算入度
	public int getInDegree(int u){
		int degree = 0;
		//计算单链表的长度
		for(int i = 0; i < count; i++){
			if(lists[i].v == u){
				GraphNode cur = lists[i];
				while(cur != null){
					degree++;
					cur = cur.next;
				}
			}
		}
		return degree;
	}
	
	// 计算入度
	public int getOutDegree(int u) {
		int degree = 0;
		// 计算单链表的长度
		for(int i = 0; i < count; i++){
			//不要从第一个开始，否则我们会将lists[u]的头结点计算在内
			GraphNode cur = lists[i].next;
			while (cur != null) {
				if(cur.v == u){
					degree++;
					break;
				}else{
					cur = cur.next;
				}
			}
		}
		return degree;
	}
}
